package com.mgq.algorithm.twotree;

/**
 * 满二叉树
 *使用DP
 *
 * 找共同点
 * 1.左树和右树都是满二叉树
 * 2.每个树的节点数N,深度L,满足的条件是: N=2^L-1
 *
 * 分析可能性
 * 2个条件都满足
 *
 * 整理条件, 左树和右树需要什么条件,才能判断
 * 1.需要返回树的节点数
 * 2.需要返回树的深度
 * 3.需要返回是否是满二叉树
 *
 * 构造返回值
 */
public class FBT {
    /**
     * 判断是否为满二叉树
     * @param root
     * @return
     */
    public boolean isFBT(TreeNode root) {
        Info data = process(root);
        return data.nodes==(1 << data.height) - 1;
    }

    /**
     * 可以简化,可以将 boolean isFBT;去掉
     * @param root
     * @return
     */
    public Info process(TreeNode root) {
        if (root == null) { //base case
            return new Info(0, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);

        //构造返回条件
        int level=Math.max(leftInfo.height,rightInfo.height)+1;
        //把自己加上
        int nodes = leftInfo.nodes + rightInfo.nodes+1;
        return new Info(level, nodes);
    }
}

class Info {
    //深度
    int height;
    //节点数
    int nodes;

  //  boolean isFBT;

    public Info(int level, int nodes) {
        this.height = level;
        this.nodes = nodes;

    }
}